import java.util.Deque;
import java.util.LinkedList;

public class LeetCode232 {
    /**
     * 队列特性
     * 1，从尾部插入数据
     * 2.从队列头部获取数据并移除
     * 3，从队列头部获取数据，不移除
     * 4，判断是否为空
     *
     * 双栈模拟队列
     * 队列头              队列尾
     * a b                  a b
     * 顶  底             底   顶
     *
     * s1                 s2
     *                     s2.push(a)
     *                     s2.push(b)
     *
     * 先把 s2 的所有元素移动到 s1 再 s1.pop
     *s1.push(s2.pop(b))
     *s1.push(s2.pop(a))
     *
     */
    LinkedList<Integer> s1 = new LinkedList<>();
    LinkedList<Integer> s2 = new LinkedList<>();

    //向队列尾添加
    public void push(int x) {
        s2.push(x);
    }
    //从队列头移除
    public int pop() {
        if(s1.isEmpty()) {
            while(!s2.isEmpty()){
                s1.push(s2.pop());
            }
        }
        return s1.pop();
    }
    //从队列有获取
    public int peek(){
        if(s1.isEmpty()) {
            while(!s2.isEmpty()){
                s1.push(s2.pop());
            }
        }
        return s1.peek();
    }
    //判断是否为空
    public boolean empty(){
    return s1.isEmpty() && s2.isEmpty();
    }
}
